package Demo2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grids int整型ArrayList<ArrayList<>>
     * @return int整型
     */

    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int n,m;
    boolean[][] check;
    public int rotApple (ArrayList<ArrayList<Integer>> grids) {
        // write code here
        n = grids.size();
        m = grids.get(0).size();
        check = new boolean[n][m];
        Queue<int[]> q = new LinkedList<>();
        int hao = 0;
//        int huai = 0;
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int in = grids.get(i).get(j);
                if(in == 1) {
                    // 完好的苹果
                    hao++;
                }else if(in == 2) {
                    // 腐烂的苹果
//                    huai++;
                    q.add(new int[] {i,j});
                    check[i][j] = true;
                }
            }
        }
        int count = -1;
        while(!q.isEmpty()) {
            int sz = q.size();
            count++;
            while(sz-- > 0) {
                int[] poll = q.poll();
                int n1 = poll[0], n2 = poll[1];
                for(int i = 0; i < 4; i++) {
                    int x = n1 + dx[i], y = n2 + dy[i];
                    if(x >= 0 && x < n && y >= 0 && y < m && !check[x][y] && grids.get(x).get(y) == 1) {
                        q.add(new int[] {x,y});
                        check[x][y] = true;
                        hao--;
                    }
                }
            }
        }
        if(hao == 0) {
            return count;
        }
        return -1;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        ArrayList<ArrayList<Integer>> grids = new ArrayList<>();
        ArrayList<Integer> a1 = new ArrayList<>();
        a1.add(2);
        a1.add(1);
        a1.add(1);
        grids.add(a1);
        ArrayList<Integer> a2= new ArrayList<>();

        a2.add(1);
        a2.add(0);
        a2.add(1);
        grids.add(a2);
        ArrayList<Integer> a3= new ArrayList<>();
        a3.add(1);
        a3.add(1);
        a3.add(1);
        grids.add(new ArrayList<>(a3));
        int ret = solution1.rotApple(grids);
        System.out.println(ret);

    }
}